#define DEBUG
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn=300000, maxm=500000, mods=998244353;

int min(int a, int b) {
  return a<b ? a : b;
}

long long qpower(long long a, long long n) {
  long long s=1;
  if (n==0) {
    return 1;
  }
  for (; n>1; n/=2) {
    if (n%2) {
      s = s*a%mods;
    }
    a = a*a%mods;
  }
  return a*s%mods;
}

class Set {
public:
  int fa[maxn+1], p;
  long long v[maxn+1][2];

  void init(int n, int p) {
    this->p = p;
    for (int i=1; i<=n; i++) {
      fa[i] = i;
      v[i][0] = qpower(p, (long long)(i-1)*n%(mods-1));
      v[i][1] = qpower(p, i);
    }
  }

  int getFa(int o) {
    if (fa[o]==o) {
      return o;
    } else {
      v[fa[o]][0] = (v[fa[o]][0]+v[o][0])%mods;
      v[fa[o]][1] = (v[fa[o]][1]+v[o][1])%mods;
      v[o][0] = v[o][1] = 0;
      return fa[o] = getFa(fa[o]);
    }
  }

  long long merge(int a, int b) {
    int x=getFa(a), y=getFa(b);
    long long ret=0;
    if (x!=y) {
      fa[y] = x;
      ret = (v[x][0]*v[y][1]%mods+v[x][1]*v[y][0]%mods)%mods;
      v[x][0] = (v[x][0]+v[y][0])%mods, v[x][1] = (v[x][1]+v[y][1])%mods;
      v[y][0] = v[y][1] = 0;
    }
    return ret;
  }
};

class Side {
public:
  int x, y, v;

  void init(int a, int b, int c) {
    x=a, y=b, v=c;
  }

  static bool cmp(Side a, Side b) {
    return a.v>b.v;
  }
};

class Graph {
public:
  int n, m, ind[maxn+1], to[2*maxm+1], link[2*maxm+1], val[2*maxm+1], id[2*maxn+1], dep[maxn+1], fa[maxn+1], fas[maxn+1];
  Side sides[maxm+1];

  void addSide(int u, int v, int w, int id) {
    m++;
    to[m] = v;
    val[m] = w;
    link[m] = ind[u];
    this->id[m] = id;
    sides[id].init(u, v, w);
    ind[u] = m;
  }

  void build(int o, int fa) {
    dep[o] = dep[fa]+1;
    for (int i=ind[o]; i; i=link[i]) {
      if (to[i]!=fa) {
	fas[to[i]] = id[i];
	build(to[i], o);
	this->fa[to[i]] = o;
      }
    }
  }

  void change(int x, int y, int v) {
    if (dep[x]<dep[y]) {
      int t;
      t=x, x=y, y=t;
    }
    for (; dep[fa[x]]>=dep[y]; x=fa[x]) {
      sides[fas[x]].v += v;
    }
    for (; x!=y; x=fa[x], y=fa[y]) {
      sides[fas[x]].v += v;
      sides[fas[y]].v += v;
    }
  }
};

void rebuild(Side dest[], Side src[], int n, int m) {
  static Graph g;
  sort(src+1, src+m+1, Side::cmp);

  static Set set;
  static bool book[maxm+1];
  set.init(n, 0);
  for (int i=1; i<=m; i++) {
    if (set.getFa(src[i].x)==set.getFa(src[i].y)) {
      book[i] = true;
    } else {
      set.merge(src[i].x, src[i].y);
      g.addSide(src[i].x, src[i].y, src[i].v, i);
      g.addSide(src[i].y, src[i].x, src[i].v, i);
    }
  }
  g.build(1, 0);

  for (int i=1; i<=m; i++) {
    if (book[i]) {
      g.change(src[i].x, src[i].y, src[i].v);
    }
  }

  int size=0;
  for (int i=1; i<=m; i++) {
    if (g.sides[i].v) {
      dest[++size] = g.sides[i];
    }
  }
}

int main() {
  freopen("sakura.in", "r", stdin);
  freopen("sakura.out", "w", stdout);

  static Side sides[maxn], inputs[maxm+1];
  int n, m, p;
  scanf("%d %d %d", &n, &m, &p);
  for (int i=1; i<=m; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    inputs[i].init(u, v, w);
  }

  rebuild(sides, inputs, n, m);
  sort(sides+1, sides+n, Side::cmp);

  static Set set;
  set.init(n, p);
  long long ans=0;
  for (int i=1; i<n; i++) {
    ans = (ans+sides[i].v*set.merge(sides[i].x, sides[i].y)%mods)%mods;
  }
  printf("%lld", ans);

  fclose(stdin);
  fclose(stdout);
  return 0;
}
